package com.lw.leetcode.binary.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * c
 * binary
 * 410. 分割数组的最大值
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/1 17:35
 */
public class SplitArray {

    public static void main(String[] args) {
        SplitArray test = new SplitArray();

        // 18
//        int[] nums = {7, 2, 5, 10, 8};
//        int m = 2;

        // 9
//        int[] nums = {1, 2, 3, 4, 5};
//        int m = 2;

        // 4
//        int[] nums = {1, 4, 4};
//        int m = 3;

        //
        int[] nums = Utils.getArr(1000, 1, 10000);
        int m = 50;

        int i = test.splitArray(nums, m);
        System.out.println(i);
    }

    public int splitArray(int[] nums, int m) {
        int end = Integer.MAX_VALUE;
        int st = 0;
        while (st < end) {
            int mid = st + ((end - st) >> 1);
            int c = 1;
            int sum = 0;
            for (int num : nums) {
                if (num > mid) {
                    c = m + 1;
                    break;
                }
                sum += num;
                if (sum > mid) {
                    sum = num;
                    c++;
                }
            }
            if (c > m) {
                st = mid + 1;
            } else {
                end = mid;
            }
        }
        return st;
    }

}
